#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;

int cal(vector<vector<int>>& grid, int i, int j, 
        int row, int col, vector<vector<int>>& mem) {
    if (i == 0 && j == 0) return grid[i][j];
    if (i < 0 || j < 0) return INT_MAX;
    if (mem[i][j] > 0) return mem[i][j];

    int res = grid[i][j] + min(cal(grid, i - 1, j, row, col, mem), cal(grid, i, j - 1, row, col, mem));
    mem[i][j] = res;
    return res;
}

int minPathSum(vector<vector<int>>& grid) {
    int row = grid.size();
    int col = grid[0].size();
    // mem
    vector<vector<int>> mem(row, vector<int>(col, 0));
    return cal(grid, row - 1, col - 1, row, col, mem);
}

int main(int argc, char const *argv[])
{
    vector<vector<int>> grid = {
                                {1,3,1},
                                {1,5,1},
                                {4,2,1}
                               };

    int pathSum = minPathSum(grid);
    cout << pathSum << endl;
    return 0;
}
